/**
 * 剑指 Offer 13. 机器人的运动范围
 * https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/
 */
public class Solutions_Offer_13 {
    public static void main(String[] args) {
        int m = 2, n = 3, k = 1;  // output: 3
//        int m = 3, n = 1, k = 0;  // output: 1
//        int m = 1, n = 3, k = 11;  // output: 3

        int result = movingCount(m, n, k);
        System.out.println(result);
    }

    public static int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        return movingCount_dfs(m, n, k, 0, 0, visited);
    }

    /**
     * 使用深度优先搜索完成“机器人的移动”
     * 1. 题目已说明了默认是从 [0, 0] 的坐标为原点
     * 2. 每次只可以向上、下、左、右移动一步，那么从原点向右及向下移动即可（因为加上了标记，那么同时递归四个方向也可以）
     * 3. 已经到达过的位置需要标记，避免重复计算及死循环
     */
    public static int movingCount_dfs(int m, int n, int k, int x, int y,
                                      boolean[][] visited) {
        // 结束条件：[x, y] 已经不在 [m - 1, n - 1] 范围内，或者已经到达过
        if (x >= m || y >= n || visited[x][y]) {
            return 0;
        }
        // 结束条件：超出范围，坐标之和大于 k
        if (x / 10 + x % 10 + y / 10 + y % 10 > k) {
            return 0;
        }
        // 标记为已访问
        visited[x][y] = true;
        // 以 [x, y] 为原点，向右递推，得到可以到达的位置数
        int rightRes = movingCount_dfs(m, n, k, x + 1, y, visited);
        // 以 [x, y] 为原点，向下递推，得到可以到达的位置数
        int downRes = movingCount_dfs(m, n, k, x, y + 1, visited);
        // 最终的能够到达的位置数 = 向右可以到达的位置数 + 向下可以到达的位置数 + 当前位置
        return rightRes + downRes + 1;
    }
}
